package Q139;

import java.util.Iterator;
import java.util.List;

/**
 * 单词拆分
 *给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
 * @author 23737
 * @time 2021.11.09
 */
public class Test {
    public static void main(String[] args) {

    }
}

/*
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if(s.length() == 0) return false;
        int begin = 0;
        int end = 1;
        for(int i=0; i<s.length(); i++) {
            for(int j=1; j<s.length(); j++) {
                String str = s.substring(begin,end);
                if (j == s.length()-1 && checkWord(str,wordDict)){
                    return true;
                }
                    if(checkWord(str,wordDict)){
                    begin = i;
                    end = j;
                    continue;
                }
            }
        }
        return false;
    }
    public boolean checkWord(String s,List<String> list) {
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            if (s == iterator.next()) {
                System.out.println("成功匹配");
                return true;
            }
        }
        return false;
    }
}
*/

/**
 * 使用动态规划
 */
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 可以类比于背包问题
        int n = s.length();
        // memo[i] 表示 s 中以 i - 1 结尾的字符串是否可被 wordDict 拆分
        boolean[] memo = new boolean[n + 1];
        memo[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (memo[j] && wordDict.contains(s.substring(j, i))) {
                    memo[i] = true;
                    break;
                }
            }
        }
        return memo[n];
    }
}